package com.example.arithmeticleetcode.leetcode.jan;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2021-01-27 10:14
 **/
public class Demo22 {

    /**
     * 744. 寻找比目标字母大的最小字母
     *
     * @param letters
     * @param target
     * @return
     */
    public char nextGreatestLetter(char[] letters, char target) {
        if (letters[0] > target || letters[letters.length - 1] < target) return letters[0];
        for (int i = 1; i < letters.length; i++) {
            if (letters[i] > target) {
                return letters[i];
            }
        }
        return letters[0];
    }


    /**
     * 374. 猜数字大小
     *
     * @param n
     * @return
     */
    public static int guessNumber(int n) {
        int start = 1;
        int end = n;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            int guess = guess(mid);
            if (guess == 0) return mid;
                //pick < mid
            else if (guess < 0) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    public static int guess(int n) {
        return n - 7;
    }


    /**
     * 392. 判断子序列
     *
     * @param s
     * @param t
     * @return
     */
    public static boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        int sIndex = 0;
        int tIndex = 0;
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        while (tIndex < tChars.length && sIndex < sChars.length) {
            if (tChars[tIndex++] == sChars[sIndex]) {
                sIndex++;
            }
        }
        return sIndex == sChars.length;
    }

    /**
     * 401. 二进制手表
     *
     * @param num
     * @return
     */
    public List<String> readBinaryWatch(int num) {

        return null;
    }

    /**
     * 1287. 有序数组中出现次数超过25%的元素
     *
     * @param arr
     * @return
     */
    public int findSpecialInteger(int[] arr) {
        int maxCount = 1;
        int eachCount = 1;
        int num = arr[0];
        int pre = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == pre) {
                eachCount++;
            } else {
                if (maxCount < eachCount) {
                    maxCount = eachCount;
                    num = pre;
                }
                eachCount = 0;
                pre = arr[i];
            }
        }
        return num;
    }


    /**
     * 1299. 将每个元素替换为右侧最大元素
     *
     * @param arr
     * @return
     */
    public static int[] replaceElements(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i + 1; j < arr.length; j++) {
                max = Math.max(max, arr[j]);
            }
            arr[i] = max;
        }
        arr[arr.length - 1] = -1;
        return arr;
    }

    /**
     * 1299. 将每个元素替换为右侧最大元素
     *
     * @param arr
     * @return
     */
    public static int[] replaceElements2(int[] arr) {
        int rightMax = arr[arr.length - 1];
        arr[arr.length - 1] = -1;
        for (int i = arr.length - 2; i >= 0; i++) {
            int t = arr[i];
            arr[i] = rightMax;
            if (t > rightMax) {
                rightMax = t;
            }
        }
        return arr;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        decompressRLElist(arr);
    }


    /**
     * 1313. 解压缩编码列表
     *
     * @param nums
     * @return
     */
    public static int[] decompressRLElist(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i += 2) {
            count += nums[i];
        }
        int[] ints = new int[count];
        count = 0;
        for (int i = 0; i < nums.length; i += 2) {
            int index = 0;
            while (index++ < nums[i]) {
                ints[count++] = nums[i + 1];
            }
        }
        return ints;
    }

}
